//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [3,2,1], k = 2
//输出：[1,2] 或者 [2,1]
// 
//
// 示例 2： 
//
// 输入：arr = [0,1,2,1], k = 1
//输出：[0] 
//
// 
//
// 限制： 
//
// 
// 0 <= k <= arr.length <= 10000 
// 0 <= arr[i] <= 10000 
// 
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 433 👎 0

package leetcode.editor.offer;

// 40. 最小的 K 个数
class ZuiXiaoDeKgeShuLcof {
    public static void main(String[] args) {
        Solution solution = new ZuiXiaoDeKgeShuLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public int[] getLeastNumbers(int[] arr, int k) {
            // 归并排序
            // mergeSort(arr, 0, arr.length - 1);

            // 快排
            quickSort(arr,k, 0, arr.length - 1);

            return Arrays.copyOf(arr, k);
        }*/

        /**
         * 归并排序
         *
         * @param nums
         * @param l
         * @param r
         */
        /*public void mergeSort(int[] nums, int l, int r) {
            if (l >= r) {
                return;
            }

            int mid = (l + r) / 2;
            mergeSort(nums, l, mid);
            mergeSort(nums, mid + 1, r);

            int[] tempArray = new int[r - l + 1];
            for (int i = l; i <= r; i++) {
                tempArray[i - l] = nums[i];
            }

            int i = 0, j = mid - l + 1; // 分别指向左右子数组的首个元素
            for (int k = l; k <= r; k++) {
                if (i == mid - l + 1) {
                    nums[k] = tempArray[j++];
                } else if (j == r || tempArray[j] >= tempArray[i]) {
                    nums[k] = tempArray[i++];
                } else if (tempArray[j] < tempArray[i]) {
                    nums[k] = tempArray[j++];
                }
            }
        }*/

        /**
         * 快速排序
         *
         * @param arr
         * @param l
         * @param r
         */
        /*public void quickSort(int[] arr, int l, int r) {
            if (l >= r) {
                return;
            }

            int i = l, j = r;
            while (i < j) {
                while (i < j && arr[j] >= arr[l]) j--;
                while (i < j && arr[i] <= arr[l]) i++;
                swap(arr, i, j);
            }
            swap(arr, l, i);    // 交换最后位置

            // 递归左右数组进行快速排序
            quickSort(arr, l, i - 1);
            quickSort(arr, i + 1, r);
        }*/

        /*public void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        */

        /**
         * 基于快速排序的数组划分
         *//*
        public void quickSort(int[] arr, int k, int l, int r) {
            if (l >= r) {
                return;
            }

            int i = l, j = r;
            while (i < j) {
                while (i < j && arr[j] >= arr[l]) j--;
                while (i < j && arr[i] <= arr[l]) i++;
                swap(arr, i, j);
            }
            swap(arr, l, i);    // 交换最后位置

            if (i > k) quickSort(arr, k, l, i - 1); // i > k,表示需要的元素在左数组
            if (i < k)quickSort(arr, k, i + 1, r);  // i < k,表示需要的元素在右数组
            // 相等表示左边就是 k 个元素,而基准此时就是 k + 1，所以直接返回前面k个数
        }*/

        // 堆
        /*public int[] getLeastNumbers(int[] arr, int k) {
            PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
            for (int i = 0; i < arr.length; i++) {
                queue.offer(arr[i]);
                if (queue.size() > k) {
                    queue.poll();
                }
            }

            int[] res = new int[k];
            for (int i = 0; i < k; i++) {
                res[i] = queue.poll();
            }

            return res;
        }*/

        // 快排
        public int[] getLeastNumbers(int[] arr, int k) {
            quickSort(arr, 0, arr.length - 1);

            int[] res = new int[k];
            for (int i = 0; i < k; i++) {
                res[i] = arr[i];
            }

            return res;
        }

        public void quickSort(int[] arr, int l, int r) {
            if (r <= l) return;

            int m = partion(arr, l, r);

            quickSort(arr, l, m - 1);
            quickSort(arr, m + 1, r);
        }

        private int partion(int[] arr, int l, int r) {
            int i = l, j = r;
            while (i < j) {
                while (i < j && arr[j] >= arr[l]) j--;
                while (i < j && arr[i] <= arr[l]) i++;
                swap(arr, i, j);
            }
            swap(arr, l, i);
            return i;
        }

        private void swap(int[] arr, int i, int j) {
            int t = arr[j];
            arr[j] = arr[i];
            arr[j] = t;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
